package com.leetcode.www;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * Creared with IntelliJ IDEA.
 * Description:给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 *
 * 请你设计并实现时间复杂度为O(n) 的算法解决此问题。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-consecutive-sequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-04-10
 * Time:22:40
 */
public class Set128 {
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
    public int longestConsecutive1(int[] nums) {
        if(nums.length == 1)return 1;
        Arrays.sort(nums);
        int count = 0;
        int i = 0;
        int j = 0;
        Set<Integer> set = new HashSet<>();
        for(int x : nums){
            set.add(x);
        }
        while(i < nums.length){
            j = i;
            while(i < nums.length && set.contains(nums[i] + 1)){
                if(i + 1 < nums.length && nums[i] == nums[i + 1]){//有重复元素不应包含在序列中
                    i ++;
                    j ++;
                }else{
                    i ++;
                }
            }
            count = Math.max(i - j + 1,count);
            i ++;
        }
        return count;
    }
}
